# coding:utf-8
def o(A,B,a,b):
	S = A*B
	F = (A-a)*(B-b)+(A-b)*(B-a)
	O = 1*(S-F)
	return O

# 用于存放剩余空间的列表
spaceOfTree = []
placingOrder = []
message = []


def packing( A, B, num1, num2, pell):
	# placingOrder.append('a')
	j = 1
	try:
		od = []
		# 筛选能放进布局空间的零件并计算出排序最靠前的布局块
		for i in pell:
			if ((A>= i[1] and B>= i[2]) or (A >= i[2] and B >= i[1])):
				c = o(A,B,i[1],i[2])
				od.append(c)
			else:
				c= o(A,B,0,0)
				od.append(c)

		# 判断，如果pell数组有能放进去的布局块就继续分割；
		# 如果没有，则表示pell数组的布局块都大于布局空间，更换布局空间
		if( (len(od)==1)and(od[0] != -A*B)):
			if ((pell[0][3]<= num1) and (pell[0][4]<=num2)):			# 满足真空嘴和热电偶数才放入包中
				numOfvacuum = num1 - pell[0][3]
				numOfGalvanic = num2 - pell[0][4]
				yo = pell[0][0]
				placingOrder.append(yo)
				message.append(placingOrder)
				if (pell[0][1] <= A and pell[0][2] <= B):
					spaceOfTree.append([A - pell[0][1], B])
					spaceOfTree.append([pell[0][1], B - pell[0][2]])
				else:
					spaceOfTree.append([A - pell[0][2], B])
					spaceOfTree.append([pell[0][2], B - pell[0][1]])
				message.append(spaceOfTree)
				message.append(numOfvacuum)
				message.append(numOfGalvanic)
			# print placingOrder
			return message
		elif ((len(od) ==1)and(od[0] ==-A*B)):
			message.append(placingOrder)
			message.append(spaceOfTree)
			message.append(num1)
			message.append(num2)
			return message

		elif (max(od) != min(od)):
			d = max(od)
			e = od.index(d)
			yo = pell[e][0]


			# 在满足真空嘴和热电偶的情况下，存放放入布局块的序号
			if ((pell[e][3]<=num1) and (pell[e][4]<=num2)):
				# 更新可以使用的真空嘴和热电偶
				numOfvacuum = num1 - pell[e][3]
				numOfGalvanic = num2 - pell[e][4]

				# 将布局快放入队列
				placingOrder.append(yo)

				# print e+1
				# print pell[e]

				# 将布局块放入后剩余的空间中
				if (pell[e][1] <= A and pell[e][2]<= B):
					spaceOfTree.append([A-pell[e][1],B])
					spaceOfTree.append([pell[e][1],B-pell[e][2]])

				else:
					spaceOfTree.append([A-pell[e][2],B])
					spaceOfTree.append([pell[e][2],B-pell[e][1]])

				# 删除已经排好的块
				pell.remove(pell[e])

				lenth1 = spaceOfTree[-1][0]
				weith1 = spaceOfTree[-1][1]
				spaceOfTree.pop()
				packing(lenth1,weith1,numOfvacuum,numOfGalvanic,pell)

			# 不满足的情况下，排除不满足的零件，并重新筛选零件
			else:
				pell.remove(pell[e])

				packing(A,B,num1,num2,pell)


		# 该句表示装入od中的最大值等于最小值，说明零件都比布局空间大，此时不消耗热电偶和真空嘴
		else:
			lenth2 = spaceOfTree[-1][0]
			weith2 = spaceOfTree[-1][1]
			spaceOfTree.pop()

			packing(lenth2,weith2,num1,num2,pell)


	except	IndexError:
		message.append(placingOrder)
		message.append(spaceOfTree)
		message.append(num1)
		message.append(num2)
		# placingOrder.append('a')
		# print placingOrder
	return message

if __name__ == '__main__':

	quadrel = [[15,0.94,0.96,2,2],[30,0.99,0.83,3,3],[38,0.68,0.02,1,3], [6,0.69,0.07,2,2], [16,0.06,0.34, 2, 2], [24, 0.71, 0.93, 2, 2]]

	print packing(2.5, 2, 30, 35, quadrel)


